public class MatrixBlockSum {
    int m; // 对应 x 坐标
    int n; // 对应 y 坐标

    public int[][] matrixBlockSum(int[][] mat, int k) {
        m = mat.length;
        n = mat[0].length;

        int[][] dp = new int[m+1][n+1];
        // 构造dp表(注意是从下标 1 开始)
        for(int i = 1; i < m+1; i++) {
            for(int j = 1; j < n+1; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1] + mat[i-1][j-1] - dp[i-1][j-1];
            }
        }

        int[][] ret = new int[m][n];
        // 求取 [k,l] 和 [i, j] 两组坐标
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                ret[i][j] = answer(dp, k, i, j);
            }
        }

        return ret;
    }

    public int answer(int[][] dp, int number, int x, int y) {
        int k = Math.max(0, x-number) + 1;
        int l = Math.max(0, y-number) + 1;

        int i = Math.min(m-1, x+number) + 1;
        int j = Math.min(n-1, y+number) + 1;

        return dp[i][j] - dp[k-1][j] - dp[i][l-1] + dp[k-1][l-1];
    }
}
